package com.jacklei.ch16;

import java.util.Arrays;
import java.util.Map;

/*
* 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
 

示例 1：


输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：


输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
 

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-a-2d-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
public class SearchA2DMatrix {
    //1.自己 想的  时间复杂度O (M * log N) 空间复杂度 O(1)
    public boolean searchMatrix(int[][] matrix, int target) {
        int M = matrix.length;
        int N = matrix[0].length;
        if(M == 1){
            if(N == 1) return matrix[0][0] == target;
            if(matrix[0][0] <= target && target <= matrix[0][N-1])
                return Arrays.binarySearch(matrix[0],0,N,target) > -1;
        }
        for (int i = 0; i < M; i++) {
                if(matrix[i][0] <= target && target <= matrix[i][N-1])
                    return Arrays.binarySearch(matrix[i],0,N,target) > -1;
        }
        return false;
    }
    // 横纵都用二分查找 时间复杂度 O(log M + logN) =O(log M *N)  空间复杂度 O(1)
    public boolean searchMatrix1(int[][] matrix, int target){
        int rowIndex = binarySearchFirstColumn(matrix,target);
        if( rowIndex < 0 )return false;


        return binarySearchRow(matrix[rowIndex], target);

    }

    private boolean binarySearchRow(int[] matrix, int target) {
        int low = 0, high = matrix.length-1;
        while (low <= high) {
            int mid = (high -low)/2 +low;
            if(matrix[mid] == target) return true;
            if(matrix[mid] > target){
                high = mid -1;
            }else {
                low = mid + 1;
            }
        }
        return false;
    }

    private int binarySearchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length -1;
        while(low < high){
            int mid = (high - low +1) /2 + low;
            if(matrix[mid][0] <= target){
                high = mid;
            }else {
                low = mid - 1;
            }
        }
        return low;
    }
    //整体当作一个一位数组的进行二分查找 时间复杂度 O(log M *N)  空间复杂度 O(1)
}
